package zuosheng.Window;

import java.util.LinkedList;

/**
 * @author lj
 * @Description: 求一个数组中最大值减去最小值小于或等于 num 的子数组数量（要求O(N)）
 * @date 2020-11-19 13:11
 * @QQ 851477108
 */


public class GetAllLessNumSubArray {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9,10};
        int num = 4;
        System.out.println(getNum1(arr,num));
        System.out.println(getNum(arr,num));
        System.out.println(getAllSubArrayLessNum(arr,num));
    }

    //O(N)
    public static int getNum(int[] arr, int num){
        if (arr == null || arr.length == 0 || num < 0){
            return 0;
        }

        LinkedList<Integer> qMin = new LinkedList<>();
        LinkedList<Integer> qMax = new LinkedList<>();

        int L = 0;
        int R = 0;
        int res = 0;

        // 每个元素都会作为子数组中的第一个元素往外扩，进行尝试
        while (L < arr.length){
            // 尝试以left开头，right往外扩
            while (R < arr.length){
                // 更新最大值双端队列
                while (!qMin.isEmpty() && arr[qMin.peekLast()] >= arr[R]) {
                    qMin.pollLast();
                }
                qMin.addLast(R);
                // 更新最小值双端队列
                while (!qMax.isEmpty() && arr[qMax.peekLast()] <= arr[R]) {
                    qMax.pollLast();
                }
                qMax.addLast(R);

                if (arr[qMax.peekFirst()] - arr[qMin.peekFirst()] > num){
                    break;
                }

                R++;// right扩
            }
            res += R - L;  // 以left开头的满足条件的子数组个数为：right - left 个

            if (qMin.peekFirst() == L) {
                qMin.pollFirst();
            }
            if (qMax.peekFirst() == L) {
                qMax.pollFirst();
            }
            L++;// left右移一位
        }
        return res;
    }

    //O(N^3)暴力遍历方法
    public static int getNum1(int[] arr,int num){
        int res = 0;
        for (int start = 0; start < arr.length; start++){
            for (int end = start; end < arr.length; end++){
                if (isValid(arr,start,end,num)){
                    res++;
                }
            }
        }
        return res;
    }

    public static boolean isValid(int[] arr, int start, int end, int num){
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = start; i <= end; i++){
            max = Math.max(max,arr[i]);
            min = Math.min(max,arr[i]);
        }
        return max - min <= num;
    }


    //其他人的
    public static int getAllSubArrayLessNum(int[] arr, int num){
        if(arr == null || arr.length == 0){
            return 0;
        }
        int left = 0;
        int right = 0;
        int res = 0;
        LinkedList<Integer> maxQueue = new LinkedList<>();  // 最大值
        LinkedList<Integer> minQueue = new LinkedList<>();  // 最小值
        // 每个元素都会作为子数组中的第一个元素往外扩，进行尝试
        while(left < arr.length){
            // 尝试以left开头，right往外扩
            while(right < arr.length){
                // 更新最大值双端队列
                while(!maxQueue.isEmpty() && arr[maxQueue.peekLast()] <= arr[right]){
                    maxQueue.pollLast();
                }
                maxQueue.addLast(right);
                // 更新最小值双端队列
                while(!minQueue.isEmpty() && arr[minQueue.peekLast()] >= arr[right]){
                    minQueue.pollLast();
                }
                minQueue.addLast(right);
                if(arr[maxQueue.peekFirst()] - arr[minQueue.peekFirst()] > num) {
                    break;
                }
                right++;
            }
            res += right - left;  // 以left开头的满足条件的子数组个数为：right - left 个
            // left右移一位
            if(left == maxQueue.peekFirst()){
                maxQueue.pollFirst();
            }
            if(left == minQueue.peekFirst()){
                minQueue.pollFirst();
            }
            left++;
        }
        return res;
    }

}
